741B - Arpa's weak amphitheater and Mehrdad's valuable Hoses - CodeForces Solution

#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
#include<functional>
#include<numeric>
#include<cmath>

using namespace std;

#define endl "\n"
#define ain(a) for(int _i=0;_i<a.size();_i++) cin >> a[_i]
#define aout(a) for(int _i=0;_i<a.size();_i++) { if(_i > 0) cout << " "; cout << a[_i]; }; cout << endl
#define couty cout << "YES\n"
#define coutn cout << "NO\n"

#define pb push_back
#define eb emplace_back
#define all(a) a.begin(),a.end()

#ifdef LOCAL_JUDGE
#include "local.hpp"
#else
template <typename Head, typename... Tail> void dout(Head&& h, Tail&&... t) {}
#endif

typedef long long ll;
typedef pair<int,int> pii; typedef pair<ll,int> pli; typedef tuple<ll,int,int> tllii;
typedef vector<int> vi; typedef vector<bool> vb; typedef vector<ll> vll; typedef vector<vector<int> > vvi; typedef vector<string> vs;

template<class T> void amin(T &a, T b) { if (a > b) a = b; }
template<class T> void amax(T &a, T b) { if (a < b) a = b; }

const ll MOD = 1e9+7;

void solve() {
	int n, m , w; cin >> n >> m >> w;
	vi hw(n); ain(hw);
	vi hb(n); ain(hb);
	vvi g(n);
	for(int i=0;i<m;i++) {
		int u,v;
		cin >> u >> v; u--, v--;
		g[u].pb(v);
		g[v].pb(u);
	}
	// dout(g);
	vi component(n,-1);
	function<void(int,int)> dfs = [&](int u,int c) {
		if(component[u] >= 0) return;
		component[u] = c;
		for(auto v:g[u]) dfs(v,c);
	};
	int cid=0;
	for(int i=0;i<n;i++) if(component[i] < 0) {
		dfs(i,cid++);
	}
	vector<vector<pii>> groups(cid);
	for(int i=0;i<n;i++) {
		int c = component[i];
		groups[c].eb(hw[i],hb[i]);
	}
	// dout(groups);
	for(auto &g:groups) {
		int tw = 0, tb = 0;
		for(auto [w,b]:g) {
			tw += w;
			tb += b;
		}
		g.eb(tw,tb);
	}
	// dout(g);
	vi dp(1+w);
	for(auto &g:groups) {
		vi pdp = dp;
		for(auto [mw,mb]:g) {
			for(int tw=0;tw<=w-mw;tw++) {
				dp[tw+mw] = max(dp[tw+mw],pdp[tw]+mb);
			}
		}
	}
	cout << dp[w] << endl;
}

int main(int argc,char *argv[]) {
#ifdef LOCAL_JUDGE
	freopen(argc > 1 ? argv[1] : "in.txt", "r", stdin);
#endif
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);cout.tie(NULL);
	int t = 1;
	// cin >> t;
	for(int i=1;i<=t;i++) {
		dout("***",i);
		solve();
	}
}